package fun.coding.leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class SurroundedRegions {

	public static void main(String[] args) {

	}
	
	// This is a very good example of BFS, the trick is start from the edge, BFS search the ones we don't want to delete
	// It is just a bit harder to do it inside since it is hard to track whether it is contained, same idea though
	public void solve(char[][] board) {
		if (board == null || board.length == 0 || board[0].length == 0) return;
		
		int row = board.length;
		int col = board[0].length;
		
		Queue<Coordinates> q = new LinkedList<Coordinates>();
		
		// Start from the edge
		for (int i = 0; i < col; i++) {
			if (board[0][i] == 'O') q.offer(new Coordinates(0, i));
			if (board[row - 1][i] == 'O') q.offer(new Coordinates(row - 1, i));
		}
		
		for (int i = 0; i < row; i++) {
			if (board[i][0] == 'O') q.offer(new Coordinates(i, 0));
			if (board[i][col - 1] == 'O') q.offer(new Coordinates(i, col - 1));
		}
		
		while (!q.isEmpty()) {
			Coordinates c = q.poll();
			board[c.x][c.y] = 'F';
			
			if (c.x - 1 >= 0 && board[c.x-1][c.y] == 'O') { // up
				q.offer(new Coordinates(c.x-1, c.y));
			}
			if (c.x + 1 <= row - 1 && board[c.x+1][c.y] == 'O') { // down
				q.offer(new Coordinates(c.x + 1, c.y));
			} 
			if (c.y - 1 >= 0 && board[c.x][c.y-1] == 'O') { // left
				q.offer(new Coordinates(c.x, c.y-1));
			} 
			if (c.y + 1 <= col - 1 && board[c.x][c.y+1] == 'O') { // right
				q.offer(new Coordinates(c.x, c.y+1));
			}
		}
		
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (board[i][j] == 'O') board[i][j] = 'X';
				if (board[i][j] == 'F') board[i][j] = 'O';
			}
		}
    }
	
	public class Coordinates {
		public int x;
		public int y;
		
		public Coordinates(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

}
